; Exercise 2.70.
;
; The following eight-symbol alphabet with associated relative
; frequencies was designed to efficiently encode the lyrics of 1950s rock
; songs. (Note that the ``symbols'' of an ``alphabet'' need not be individual
; letters.)

; A     2 NA   16
; BOOM  1 SHA  3
; GET   2 YIP  9
; JOB   2 WAH  1

; Use generate-huffman-tree (exercise 2.69) to generate a corresponding Huffman
; tree, and use encode (exercise 2.68) to encode the following message:

; Get a job

; Sha na na na na na na na na

; Get a job

; Sha na na na na na na na na

; Wah yip yip yip yip yip yip yip yip yip

; Sha boom

; How many bits are required for the encoding? What is the smallest number of
; bits that would be needed to encode this song if we used a fixed-length code
; for the eight-symbol alphabet?
; ------------------------------------------------------------

(load "../helpers.scm")
(load "2.3.scm")
(load "example-huffman.scm")
(load "e-2.68.scm")

(define text
  (list
    '(Get a job)
    '(Sha na na na na na na na na)
    '(Get a job)
    '(Sha na na na na na na na na)
    '(Wah yip yip yip yip yip yip yip yip yip)
    '(Sha boom)))

(define symbol-list
  (list (list 'a 2)
        (list 'na 16)
        (list 'boom 1)
        (list 'Sha 3)
        (list 'Get 2)
        (list 'yip 9)
        (list 'job 2)
        (list 'Wah 1)))

(define h-tree (generate-huffman-tree symbol-list))

(define (encode-symbol-list symbols tree)
  (if (null? symbols)
    '()
    (append (encode (car symbols) tree)
            (encode-symbol-list (cdr symbols) tree))))

(define res (encode-symbol-list symbol-list h-tree))

; Given the most optimal Huffman tree, which is generated by our very cool optimal procedure
; we get the 55 bits for the encoding of the message.
(output res)
(output (length res))

; If we would use fixed encoding it would take 36*3 bits which is 108, almost 100% increase.
; So we save 50% of space by using this approach.
